package primary.primary0;

import offer.offer02.TreeNode;

public class S0124二叉树中的最大路径和 {

    /**
     * 答案，是一样的
     */
    class Solution {
        int maxSum = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            maxGain(root);
            return maxSum;
        }

        public int maxGain(TreeNode node) {
            if (node == null) {
                return 0;
            }

            // 递归计算左右子节点的最大贡献值
            // 只有在最大贡献值大于 0 时，才会选取对应子节点
            int leftGain = Math.max(maxGain(node.left), 0);
            int rightGain = Math.max(maxGain(node.right), 0);

            // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            // mark:其实每个节点只算当前节点的时候，就已经没有子节点最大值返回了0会导致的问题了，因为这个0不会参与最大值计算，0相当于没有选择子节点，参与计算的还是当前节点
            int priceNewpath = node.val + leftGain + rightGain;

            // 更新答案
            maxSum = Math.max(maxSum, priceNewpath);

            // 返回节点的最大贡献值
            return node.val + Math.max(leftGain, rightGain);
        }
    }


    class Solution2 {
        /**
         * 二叉树遍历，肯定是后序遍历
         * 每个子节点，返回当前如果当前节点在路径中的话，最大值
         * 并且每个节点计算当前节点，算上左右两个子树的话，可以构成的最大路径和，但是注意返回给上一层的时候只能挑一个子树来算
         */
        public int maxPathSum(TreeNode root) {
            if(root == null){
                return -1;
            }
            maxVal = root.val;
            calcuCurNode(root);
            return maxVal;
        }

        private int maxVal = 0;

        private int calcuCurNode(TreeNode node){
            // 因为子节点可能为负数，所以我这里判断了每个子节点是否存在，这种操作是多余的，因为每次计算的时候，都需要把当前node值加上去，
            // 比如如果没有任何一个节点是正数的话，最大值也会是负数
            maxVal = Math.max(maxVal, node.val);
            int curMax = node.val;
            if(node.left != null && node.right != null){
                int leftMax = calcuCurNode(node.left);
                int rightMax = calcuCurNode(node.right);
                maxVal = Math.max(maxVal, Math.max(node.val + leftMax, Math.max(node.val + rightMax, node.val + leftMax + rightMax)));
                curMax = Math.max(node.val, Math.max(node.val + leftMax, node.val + rightMax));
            }else if(node.left != null){
                int leftMax = calcuCurNode(node.left);
                maxVal = Math.max(maxVal, node.val + leftMax);
                curMax = Math.max(node.val, node.val + leftMax);
            }else if(node.right != null){
                int rightMax = calcuCurNode(node.right);
                maxVal = Math.max(maxVal, node.val + rightMax);
                curMax = Math.max(node.val, node.val + rightMax);
            }else{

            }
            return curMax;

        }

    }
    class Solution1 {
        /**
         * 这个return 0 不好搞，改成solution2
         * 二叉树遍历，肯定是后序遍历
         * 每个子节点，返回当前如果当前节点在路径中的话，最大值
         * 并且每个节点计算当前节点，算上左右两个子树的话，可以构成的最大路径和，但是注意返回给上一层的时候只能挑一个子树来算
         */
        public int maxPathSum(TreeNode root) {
            if(root == null){
                return -1;
            }
            maxVal = root.val;
            calcuCurNode(root);
            return maxVal;
        }

        private int maxVal = Integer.MIN_VALUE;

        private int calcuCurNode(TreeNode node){
            if(node == null){
                // 不能这么算，也会把负数变成0，
                return 0;
            }
            int leftMax = calcuCurNode(node.left);
            int rightMax = calcuCurNode(node.right);
            // 这里也不用算那么多，只需要考虑包含当前节点的就行，其他的遍历到其他值的时候会算的
            maxVal = Math.max(maxVal, Math.max(leftMax, Math.max(rightMax, Math.max(leftMax + node.val, Math.max(rightMax + node.val, leftMax + rightMax + node.val)))));
            // 这里不能和0取max，否则如果全负数的话，最大值会变成0
            return Math.max(node.val, Math.max(node.val + leftMax, node.val + rightMax));

        }
    }
}
